前言

一边学习 Datalog/Doop 一边复现论文，看了些论文补充知识，做了些实验验证理解。中文资料少就算了，英文资料也没有非常系统的，于是经常在频道里提问🤣。在这上面花了大约一整个月的时间，然后还没有复现出来… 被抓去学 Soot 做分析，但是确认了想法之后发现用 Soot 还得实现过程内数据流分析，而这只是分析的第一步，涉及到过程间的数据流那不还得再实现一遍过程间分析？

不知道之后怎么安排，反正既然都用了这么久，就把理解的内容梳理一下，自己用的时候也方便检索。

安装

使用 Doop 前需要安装 Datalog 引擎，由于默认的 souffle 不支持 Windows，因此建议在 Linux 环境下使用。

Doop 支持两个引擎：商业的 LogicBlox 和开源的 souffle，默认使用 souffle。

之前已经梳理过两个引擎的使用，不了解的可以先看一下基本语法：

Doop 从 LogicBlox 迁移到 souffle 的原因：Porting Doop to Souffle: A Tale of Inter-Engine Portability for Datalog-Based Analyses，也有文章提过 souffle 的执行速度更快。

1. 安装 souffle 引擎

目前支持 1.5.1、2.0.2、2.1（下面的安装指令可能会直接安装最新版的）

1
2
curl -s https://packagecloud.io/install/repositories/souffle-lang/souffle/script.deb.sh | sudo bash
sudo apt-get install souffle

可能会出现错误，这个得等 souffle 那边修复xd

2. 安装 doop

拉取仓库就可以了，注意需要安装 java8

1
2
3
4
5
# 安装 java8
sudo apt install java-8-openjdk

# 下载仓库
git clone https://bitbucket.org/yanniss/doop.git

使用方式

基本说明

进入 doop 源码目录下使用，./doop --help all 查看所有帮助信息。

1
2
cd doop
./doop --help all

首先 -a,--analysis <NAME> 用于指定分析，通常情况下，敏感度上去了分析耗时也就上去了，因此我个人一般只用 context-insensitive 上下文不敏感分析。有关使用 Datalog 进行指针分析可以看 Pointer Analysis。

注：LB analyses 之后的是适用于 LogicBlox 的分析选项。

1
2
3
4
5
6
7
8
9
10
11
-a,--analysis <NAME>                                      The name of the analysis. Valid values: 1-call-site-sensitive, 1-call-site-sensitive+heap, 1-object-1-type-sensitive+heap, 1-object-sensitive,
                                                          1-object-sensitive+heap, 1-type-sensitive, 1-type-sensitive+heap, 2-call-site-sensitive+2-heap, 2-call-site-sensitive+heap, 2-object-sensitive+2-heap,
                                                          2-object-sensitive+heap, 2-type-object-sensitive+2-heap, 2-type-object-sensitive+heap, 2-type-sensitive+heap, 3-object-sensitive+3-heap,
                                                          3-type-sensitive+2-heap, 3-type-sensitive+3-heap, adaptive-2-object-sensitive+heap, basic-only, context-insensitive, context-insensitive-plus,
                                                          context-insensitive-plusplus, data-flow, dependency-analysis, fully-guided-context-sensitive, micro, partitioned-2-object-sensitive+heap,
                                                          selective-2-object-sensitive+heap, sound-may-point-to, sticky-2-object-sensitive, types-only, xtractor, ----- (LB analyses) -----,
                                                          2-object-sensitive+heap-plus, adaptive-insens-2objH, adaptive2-insens-2objH, must-point-to, naive, paddle-2-object-sensitive, paddle-2-object-sensitive+heap,
                                                          partial-insens-s2objH, refA-2-call-site-sensitive+heap, refA-2-object-sensitive+heap, refA-2-type-sensitive+heap, refB-2-call-site-sensitive+heap,
                                                          refB-2-object-sensitive+heap, refB-2-type-sensitive+heap, scc-2-object-sensitive+heap, selective-2-type-sensitive+heap, selective_A-1-object-sensitive,
                                                          selective_B-1-object-sensitive, special-2-object-sensitive+heap, stutter-2-object-sensitive+heap, uniform-1-object-sensitive,
                                                          uniform-2-object-sensitive+heap, uniform-2-type-sensitive+heap

从上往下列举可能会用到的一些选项，--android 表示分析安卓程序；--app-only 表示解析应用程序输入，忽略 JDK；--cfg 表示生成控制流图；--dry-run 生成事实，不执行分析；--extra-logic 用于添加自己的 Datalog 规则；--gen-opt-directives 添加用于调优的关系。

1
2
3
4
5
6
--android                                              Force Android mode for code inputs that are not in .apk format.
--app-only                                             Only analyze the application input(s), ignore libraries/platform.
--cfg                                                  Perform a CFG analysis.
--dry-run                                              Do a dry run of the analysis (generate facts and compile but don't run analysis logic).
--extra-logic <FILE>                                   Include files with extra rules.
--gen-opt-directives                                   Generate additional relations for code optimization uses.

-h 帮助信息可以分类查看；-i 指定输入，甚至可以是 maven-id（例如，commons-collections:commons-collections:3.1）；--id 用于指定输出文件夹的名称，默认随机长串；-L 改变日志级别；--max-memory 设置内存消耗上限，推测不指定就是无上限（因为跑到过 800G 内存）；--platform 默认 Java8 不用设置；-t 默认超时时间 90min；-v 打印版本信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-h,--help <SECTION>                                       Display help and exit. Valid values: all, configuration, data-flow, datalog-engine, entry-points, fact-generation, heap-snapshots, information-flow,
                                                          native-code, open-programs, python, reflection, server-logic, statistics, xtras
-i,--input-file <INPUT>                                   The (application) input files of the analysis. Accepted formats: .jar, .war, .apk, .aar, maven-id
   --id <ID>                                              The analysis id. If omitted, it is automatically generated.
-L,--level <LOG_LEVEL>                                    Set the log level: debug, info or error (default: info).
-l,--library-file <LIBRARY>                               The dependency/library files of the application. Accepted formats: .jar, .apk, .aar
   --max-memory <MEMORY_SIZE>                             The maximum memory that the analysis can consume (does not include memory needed by fact generation). Example values: 2m, 4g.
   --platform <PLATFORM>                                  The platform on which to perform the analysis. For Android, the plaftorm suffix can either be 'stubs' (provided by the Android SDK), 'fulljars' (a custom
                                                          Android build), or 'apks' (custom Dalvik equivalent). Default: java_8. Valid values: java_3, java_4, java_5, java_6, java_7, java_7_debug, java_8,
                                                          java_8_debug, java_8_mini, java_9, java_10, java_11, java_12, java_13, java_14, java_15, java_16, android_22_fulljars, android_25_fulljars, android_2_stubs,
                                                          android_3_stubs, android_4_stubs, android_5_stubs, android_6_stubs, android_7_stubs, android_8_stubs, android_9_stubs, android_10_stubs, android_11_stubs,
                                                          android_12_stubs, android_13_stubs, android_14_stubs, android_15_stubs, android_16_stubs, android_17_stubs, android_18_stubs, android_19_stubs,
                                                          android_20_stubs, android_21_stubs, android_22_stubs, android_23_stubs, android_24_stubs, android_25_stubs, android_26_stubs, android_27_stubs,
                                                          android_28_stubs, android_29_stubs, android_25_apks, android_26_robolectric, python_2
-t,--timeout <TIMEOUT>                                    The analysis execution timeout in minutes (default: 90 minutes).
-v,--version                                              Display version and exit.

数据流分析相关选项，没有用过。

1
2
--data-flow-goto-lib                                   Allow data-flow logic to go into library code using CHA.
--data-flow-only-lib                                   Run data-flow logic only for library code.

针对 souffle 引擎的选项，可以用 --souffle-jobs 指定更多的并行空间，前提是分析能够有这么多并行，否则也不会达到指定的数量。

1
--souffle-jobs <NUMBER>                                Specify number of Souffle jobs to run (default: 4).

分析的入口点选择，没有用过，貌似不指定寻找 main 类就触发 open-program 分析。

1
2
3
4
5
--discover-main-methods                                Discover main() methods.
--discover-tests                                       Discover and treat test code (e.g. JUnit) as entry points.
--exclude-implicitly-reachable-code                    Don't make any method implicitly reachable.
--ignore-main-method                                   If main class is not given explicitly, do not try to discover it from jar/filename info. Open-program analysis variant may be triggered in this case.
--main <MAIN>                                          Specify the main class(es) separated by spaces.

关于事实的生成，Doop 中的事实是基于 Soot 的分析生成。--fact-gen-cores 可以用来增加并行度，同样，分析达不到这么多并行那也不会达到指定数量；--facts-only 只生成事实；--generate-jimple 生成事实和 Jimple/Shimple 文件；--wala-fact-gen 选用 WALA 生成事实。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
--also-resolve <CLASS>                                 Force resolution of class(es) by Soot.
--cache                                                The analysis will use the cached facts, if they exist.
--dont-cache-facts                                     Don't cache generated facts.
--extract-more-strings                                 Extract more string constants from the input code (may degrade analysis performance).
--fact-gen-cores <NUMBER>                              Number of cores to use for parallel fact generation.
--facts-only                                           Only generate facts and exit.
--generate-jimple                                      Generate Jimple/Shimple files along with .facts files.
--input-id <ID>                                        Import facts from dir with id ID and start the analysis. Application/library inputs are ignored.
--report-phantoms                                      Report phantom methods/types during fact generation.
--thorough-fact-gen                                    Attempt to resolve as many classes during fact generation (may take more time).
--unique-facts                                         Eliminate redundancy from .facts files.
--wala-fact-gen                                        Use WALA to generate the facts.
--Xfacts-subset <SUBSET>                               Produce facts only for a subset of the given classes. Valid values: PLATFORM, APP, APP_N_DEPS
--Xignore-factgen-errors                               Continue with analysis despite fact generation errors.
--Xsymlink-input-facts                                 Use symbolic links instead of copying cached facts. Used with --cache or --input-id.

如果没有指定入口或没有找到 main，将默认启用 --open-programs xxx 寻找分析的入口点；其他两个选项没用过，也没说明。

1
2
3
--open-programs <STRATEGY>                             Create analysis entry points and environment using various strategies (such as 'concrete-types' or 'jackee').
--open-programs-context-insensitive-entrypoints
--open-programs-heap-context-insensitive-entrypoints

支持分析反射的一些选项，弄不清每个选项都包含什么分析的情况下，一律建议使用 --reflection-classic。

1
2
3
4
5
6
7
8
9
10
11
12
13
--distinguish-reflection-only-string-constants         Merge all string constants except those useful for reflection.
--distinguish-string-buffers-per-package               Merges string buffer objects only on a per-package basis (default behavior for reflection-classic).
--light-reflection-glue                                Handle some shallow reflection patterns without full reflection support.
--reflection                                           Enable logic for handling Java reflection.
--reflection-classic                                   Enable (classic subset of) logic for handling Java reflection.
--reflection-dynamic-proxies                           Enable handling of the Java dynamic proxy API.
--reflection-high-soundness-mode                       Enable extra rules for more sound handling of reflection.
--reflection-invent-unknown-objects
--reflection-method-handles                            Reflection-based handling of the method handle APIs.
--reflection-refined-objects
--reflection-speculative-use-based-analysis
--reflection-substring-analysis                        Allows reasoning on what substrings may yield reflection objects.
--tamiflex <FILE>                                      Use file with tamiflex data for reflection.

--stats none 可以用于关闭统计。

1
--stats <LEVEL>                                        Set statistics collection logic. Valid values: none, default, full

形如 --X... 的选项是实验性选项，不一定支持所有分析。这些参数可能是一条 commit 增加的小功能，不建议使用，因为这些参数本身就只用于特定分析。

分析逻辑

Doop 执行流程大致可以分为三步：

  1. 使用 soot 生成 jimple 文件
    • 使用 --generate-jimple 参数可以输出 jimple 文件，在 output/<ID>/database/jimple 文件夹下
  2. 将 jimple 文件转换为 datalog 引擎的输入事实（.facts）
  3. 使用 souffle 引擎执行选定的分析，将关系输出为 .csv，即分析结果

Doop 分析字节码（或 Android 的 Dex 代码），两者都被转换为名为 Jimple 的中间表示（Intermediate Representation, IR），实际分析的就是 jimple；因为字节码是基于堆栈的，但指针分析中需要变量/局部变量来分析指向，所以使用 Soot 将基于堆栈的字节码转换为具有局部变量的中间表示。下一步将 Jimple 中间表示转换为 .facts 文件（数据库表），然后由 Datalog 逻辑加载这些文件作为输入。Datalog 从输入开始推导事实，填充关系；一些关系使用 .output 标记输出，保存为 .csv 文件；当 Datalog 执行终止时，保存的 .csv 文件就是分析输出。

执行结果

一个简单的例子，保存为 Main.java 并生成 test.jar 包。

1
2
3
4
5
6
7
8
9
10
import java.util.ArrayList;
import java.util.List;

public class Main {
   public static List<String> list = new ArrayList<>();
    public static void main(String[] args) {
        list.add("test");
        System.out.println(list);
    }
}

-i 指定分析的 jar 包；-a context-insensitive 使用上下文不敏感分析；--stats none 关闭统计信息；--generate-jinple 生成 Shimple/Jimple 文件；--fact-gen-cores 32 --souffle-jobs 32 最大并行任务数量；--id test 指定输出文件夹 test。

1
2
# 耗时 4m 24s
./doop -i test.jar -a context-insensitive --stats none --generate-jimple --fact-gen-cores 32 --souffle-jobs 32 --id test

分析完毕后，./doop/last-analysis/ 将链接到最新的分析结果，即 ./doop/out/test/database，每次分析都将在 out 目录下生成一个 目录，包含输出的数据库（database）、规则文件（xxxanalysis.dl、gen_*.dl）、元数据文件（meta）。

需要注意的是，可能是因为没有启用 --discover-main-methods 选项，所以警告没找到 main 类，并默认触发 --open-programs xxx，可以显式关闭 --open-programs disabled。使用的配置可以在元数据文件中查看，这里用的是 jackee：

1
grep -e "OPEN" out/test/meta

如果指定生成 Jimple/Shimple 文件，那么 database 文件夹下会多出一个 jimple 文件夹；souffle 分析使用的是 gen_*.dl 文件，可以用于查看命名空间。

database 文件夹中包含 .facts 事实文件，以及输出 .csv，输出是在 dl 规则文件中指定，可以编写自定义的规则文件并使用 --extra-logic myrules.dl 合并分析。

事实和输出的内容格式可以在 doop/souffle-logic/ 目录下搜索，或直接查看 gen_*.dl 文件，其中 ? 开头表示变量名（一种约定，没有为什么）。

以 AnyCallGraphEdge 为例，声明包含调用语句、方法两个参数，定义为其他调用边的并集，最后用 .output 输出到 csv 文件。

1
2
3
4
5
6
7
.decl AnyCallGraphEdge(?instr:Instruction, ?method:Method)
AnyCallGraphEdge(?i, ?m) :- CallGraphEdge(_, ?i, _, ?m).
AnyCallGraphEdge(?i, ?m) :- InvokedynamicBootCallGraphEdge(_, ?i, _, ?m).
AnyCallGraphEdge(?i, ?m) :- LambdaCallGraphEdge(_, ?i, _, ?m, _).
AnyCallGraphEdge(?i, ?m) :- MethodHandleCallGraphEdge(_, ?i, _, ?m, _, _).
AnyCallGraphEdge(?i, ?m) :- OpaqueCallGraphEdge(?i, ?m).
.output AnyCallGraphEdge(IO="file",filename="AnyCallGraphEdge.csv",delimiter="\t")

构造调用图

那么能不能直接用调用边 AnyCallGraphEdge 构造调用图呢，答案是不行，因为是语句指向方法，而不是方法指向方法。因此，这里就可以试一试自定义规则了~

首先找到语句所包含的方法调用，用关系 Instruction_Method 就可以定位，然后将二者进行匹配连接，最后输出 方法 -> 方法 作为调用图。这里的 Method 是 Doop 定义的类型，表示方法（实际上就是字符串 .type Method = symbol），而变量 ?invocation 表示指令语句（实际上也是字符串 .type Instruction = symbol）。

1
2
3
4
5
6
7
.decl CG(?caller:Method, ?callee:Method)

CG(?caller, ?callee) :-
  mainAnalysis.AnyCallGraphEdge(?invocation, ?callee),
  Instruction_Method(?invocation, ?caller).

.output CG

将上述规则保存到 myrules.dl 文件中，重新执行分析，--extra-logic myrules.dl 表示添加自定义的规则。经测试，默认 --open-programs jackee 生成的调用图中无法找到 Main 类相关的调用，使用 --open-programs concrete-types 即可，但分析耗时增加。

1
2
# 耗时 6m 2s
./doop -i test.jar -a context-insensitive --stats none --generate-jimple --fact-gen-cores 32 --souffle-jobs 32 --open-programs concrete-types --extra-logic myrules.dl --id cg

最后可以在调用图中查找 Main 类相关的调用：

1
grep -e "Main:" out/cg/database/CG.csv

查找关系

声明了一个名为 IsSerializable 的关系，定义为 java.io.Serializable 的子类，输出结果将会是可序列化类。

  • basic.SubtypeOf 表示 basic 命名空间（组件）下的 SubtypeOf 关系，包含类之间的继承关系
1
2
3
4
5
6
7
.decl IsSerializable(?class:Type)

IsSerializable(?subtype) :-
  basic.SubtypeOf(?subtype, ?type),
  ?type = "java.io.Serializable".

.output IsSerializable

保存到 myrules.dl 中，执行同样的分析。

1
2
# 耗时 5m59s
./doop -i test.jar -a context-insensitive --stats none --generate-jimple --fact-gen-cores 32 --souffle-jobs 32 --open-programs concrete-types --extra-logic myrules.dl --id ser

能够得到预期的结果：

结语

拖了一个月终于写了点东西（摊手），实际上对 Doop 规则的理解全靠阅读 doop/souffle-logic 中的 datalog 以及在 Discord 频道里进行提问，至少现在能够看懂大部分规则，也能够根据需求写一写简单的规则了。

分析比较耗时和不直观，据说是最先进的指针分析工具，但上手实在是困难。

参阅

基本就是根据工具本身和相关论文摸索出来的。